package com.javabase.y2022.m05.day0517.v6;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/17 下午 01:52
 * @version: 1.0
 */
public class Solution {

    public static void main(String[] args) {
//        int[] arr = new int[]{3,1,7,0,2};
        int[] arr = new int[]{3,1};
        System.out.println(new Solution().mergeSort01(arr));
    }

    public int mergeSort01(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        return process(arr, L, R);
    }

    public int process(int[] arr, int L, int R) {
        if(L==R){
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process(arr, L, M) +
        process(arr, M + 1, R) +
        merge(arr, L, M, R);
    }

    public int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L, p2 = M+1;
        int i = 0;
        int ans = 0;
        int windowR = M + 1;
        for (int windowL = L; windowL <= M; windowL++) {
            while (windowR <= R && arr[windowL] > arr[windowR]*2){
                windowR++;
            }
            ans += windowR - M - 1;
        }
        while(p1<= M && p2 <=R){
            help[i++] = arr[p1] < arr[p2]? arr[p1++]: arr[p2++];
        }
        while(p1<=M){
            help[i++] = arr[p1++];
        }
        while(p2<=R){
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L+j] = help[j];
        }
        return ans;
    }
}
